---
title: "L2-038 病毒溯源"
created: 2025-11-28
tags:
  - 算法
---

# L2-038 病毒溯源

## 题目 [L2-038 病毒溯源](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=1386335159927652361&page=1)

![[image-288fa884.png]]

## 思路分析

![[image-67070e97.png]]

找入度为0的是起点

## 代码实现

```cpp
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

#define int long long

using ll = long long;

using ull = unsigned long long;

using PII = pair<int, int>;

using Pll = pair<ll, ll>;

int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };

const int inf = 0x3f3f3f3f;

int maxDeep=-inf;

vector<set<int>> g;

vector<int> path;

vector<int> ans;

vector<bool> visited;

void dfs(int cur,int deep){

	if(deep>maxDeep){

		ans=path;

		maxDeep=deep;

	}

	for(auto ne:g[cur]){

		if(!visited[ne]){

			visited[ne]=true;

			path.push_back(ne);

			dfs(ne,deep+1);

			path.pop_back();

			visited[ne]=false;

		}

	}

}

signed main() {

    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;cin>>n;

	g.resize(n);

	visited.resize(n,false);

	vector<int> indegree(n);

	for(int i=0;i<n;i++){

		int k;cin>>k;

		while(k--){

			int ne;cin>>ne;

			g[i].insert(ne);

			indegree[ne]++;

		}

	}

	int start=-1;

	for(int i = 0; i < n; i++) {

		if(indegree[i] == 0) {

			start = i;

			break;

		}

	}

//	cout<<start;

	dfs(start,1);

	cout<<maxDeep<<endl;

	cout<<start;

	for(auto v:ans){

		cout<<" "<<v;

	}

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-037 包装机|L2-037 包装机]] 🏠 [[00-天梯赛]] ➡️ [[L2-039 清点代码库|L2-039 清点代码库]]